package offer;

/**
 * @author SSK
 *数组中的逆序对 数据范围不对
 */
public class T36 {
    public int InversePairs(int [] array) {
        final int MOD = 1000000007;
        final int N = 200007;
        int sum[] = new int[N];
        long ans = 0;
        for (int i = 0; i < array.length; i++) {
            add(sum,array[i]+1,N-1,1);
            ans += (query(sum,N-1,MOD) - query(sum,array[i]+1,MOD)+MOD)%MOD;
            ans %= MOD;
        }
        return (int) ans;
    }
    public void add(int[] array,int x,int n,int val) {
        while (x<=n) {
            array[x]+=val;
            x+=x&-x;
        }
    }
    public long query(int[] array, int x,int mod) {
        long ans = 0;
        while (x>0) {
            ans+=array[x];
            ans%=mod;
            x-=x&-x;
        }
        return ans;
    }
    public int InversePairs2(int [] array) {
        return merge(array,0,array.length-1,1000000007);
    }
    public int merge(int array[],int l,int r,int mod) {
        if (l>=r) {
            return 0;
        }
        int ans = 0;
        int mid = (l + r) >> 1;
        int rs = mid+1;
        int ls = l;

        ans+=merge(array,l,mid,mod);
        ans%=mod;
        ans+=merge(array,mid+1,r,mod);
        ans%=mod;
        int[] tempArray = new int[r-l+2];
        int cnt = 0;
        while (ls<=mid&&rs<=r) {
            if (array[ls]<=array[rs]) {
                tempArray[cnt] = array[ls];
                ls++;
                cnt++;
            }else {
                ans += (mid+1-ls);
                ans%=mod;
                tempArray[cnt] = array[rs];
                rs++;
                cnt++;
            }
        }
        while (ls<=mid){
            tempArray[cnt] = array[ls];
            ls++;
            cnt++;
        }
        while (rs<=r) {
            tempArray[cnt] = array[rs];
            rs++;
            cnt++;
        }
        for (int i = 0; i < cnt; i++) {
            array[i+l] = tempArray[i];
        }
        return ans;
    }
    public static void main ( String[] args) {
        System.out.println(new T36().InversePairs2(new int[]{1,2,3,4,5,6,3,0}));
    }
}
